package com.c2b.algorithm.newcoder;

/**
 * <a href='https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=295&tqId=23286&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj'>BM10 两个链表的第一个公共结点</a>
 *
 * @author c2b
 * @since 2024/3/14 11:00
 */
public class BM10FindFirstCommonNode {
    public static class Solution {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            if (pHead1 == null || pHead2 == null) {
                return null;
            }
            // 记录两个链表的差值步
            int diff = 0;
            ListNode currNode = pHead1;
            while (currNode != null) {
                currNode = currNode.next;
                ++diff;
            }
            currNode = pHead2;
            while (currNode != null) {
                currNode = currNode.next;
                --diff;
            }
            // 这种情况下，pHeader1是较长的链表
            if (diff > 0) {
                for (int i = 0; i < diff; i++) {
                    pHead1 = pHead1.next;
                }
            }
            // 这种情况下，pHeader2是较长的链表
            if (diff < 0) {
                for (int i = 0; i < -diff; i++) {
                    pHead2 = pHead2.next;
                }
            }
            // 两条链表同时走，第一个相等的节点即是公共节点。
            while (pHead1 != pHead2) {
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
            return pHead1;
        }
    }
}
